Основне статистике (збир, производ, просек, минумум, максимум)
Најчешће коришћени итеративни алгоритми служе за израчунавање статистика бројевних серија. На пример, једну такву серију могу чинити бројеви 1, 2, 3, 4 и 5. Најзначајније статистике су:
- збир елемената (збир бројева из примера је 15),
- производ елемената (производ бројева из примера је 120),
- минимум тј. најмањи од свих елемената (миминум бројева из примера је 1),
- максимум тј. највећи од свих елемената (максимум бројева из примера је 5).
Одређивање збира и производа
На примеру четворочлане серије елемената, прикажимо итеративне алгоритме за одређивање збира и производа. Збир четири броја се најједноставније израчунава изразом
broj1 + broj2 + broj3 + broj4што је због леве асоцијативности сабирања (у програмирању) идентично изразу
((broj1 + broj2) + broj3) + broj4Други начин да се израчунавање збира реализује је да се уведе помоћна
променљива zbir која би се увећавала за текући елемент.
zbir = broj1;
zbir = zbir + broj2;
zbir = zbir + broj3;
...За разлику од полазног решења у ком се збир израчунава само помоћу
једног израза, ово решење је итеративно, и резултат се добија
узастопном применом корака истог облика. Истакнимо још једном врло важну
особину итеративних алгоритама, а то је да се током њиховог извршавања
мења вредност неке променљиве (у овом случају то је променљива
zbir).
Уместо да збир иницијализујемо првим елементом, можемо га иницијализовати нулом, а затим увећавати за један по један елемент.
zbir = 0;
zbir = zbir + broj1;
zbir = zbir + broj2;
...Производ се одређује по веома сличном принципу, осим што уместо иницијализације нулом користимо иницијализацију јединицом (као неутралним елементом за множење) и што уместо сабирања користимо множење.
proizvod = 1;
proizvod = proizvod * broj1;
proizvod = proizvod * broj2;
...У задацима је често потребно израчунати просек тј. аритметичку средину серије елемената, која је једнака количнику збира и броја елемената. Приликом имплементације потребно је једино обратити пажњу да се пре дељења осигура да је било збир, било број елемената серије реалан број, да не би дошло до целобројног дељења.
Одређивање минимума и максимума
Потпуно аналогно израчунавању збира неколико бројева, може се израчунати минимум, једино што се уместо операције сабирања два броја користи операција одређивања минимума два броја. У сваком кораку се рачуна минимум минимума свих претходних бројева и текућег броја.
Реално је претпоставити да на располагању имамо функцију којом се
израчунава минимум два броја. Таква функција је обично део стандардне
библиотеке, а када није, једноставно се може дефинисати.
У језику C++ минимум два броја може се израчунати
библиотечком функцијом min која је декларисана у заглављу
<algorithm>. Минимум четири броја
онда можемо одредити наредним изразом.
min(min(min(broj1, broj2), broj3), broj4)Максимум израчунавамо по потпуно истом принципу, једино што уместо минимума два броја у сваком кораку користимо максимум два броја.
И у случају налажења минимума уместо једног израза можемо дефинисати и итеративни алгоритам.
minimum = broj1;
minimum = min(minimum, broj2);
minimum = min(minimum, broj3);
...Ако би се уместо функције за рачунање минимума два броја употребило гранање (овај пут изражено условним изразом), дошло би се до следећег кода.
minimum = broj1;
minimum = broj2 < minimum ? broj2 : minimum;
minimum = broj3 < minimum ? broj3 : minimum;
...Ако би се уместо условног израза користила наредба гранања, добио би се следећи облик кода.
minimum = broj1;
if (broj2 < minimum)
minimum = broj2;
else
minimum = minimum;
if (broj3 < minimum)
minimum = broj3;
else
minimum = minimum;
...Јасно је да гране else немају никакав ефекат и могу се
изоставити. Тиме добијамо уобичајени алгоритам одређивања минимума.
minimum = broj1;
if (broj2 < minimum)
minimum = broj2;
if (broj3 < minimum)
minimum = broj3;
...Дакле, променљиву minimum иницијализујемо вредношћу
првог броја, а затим је редом поредимо са другим, трећим, четвртим и
петим бројем и када год је неки од тих бројева мањи од дотадашње
вредности минимума тј. вредности променљиве minimum,
ажурирмо вредност те променљиве и постављамо је на број за који смо
открили да је мањи од ње.
Можемо и мало прецизније да анализирамо претходни кôд и да докажемо
његову коректност. У првом кораку вредност променљиве
minimum биће минимум једночланог скупа
{broj1}, у другом биће минимум двочланог скупа
{broj1, broj2}, након трећег биће минимум скупа
{broj1, broj2, broj3} и тако даље. Такав услов, дакле, важи
у сваком кораку нашег програма и назива се инваријанта. Ако је,
на пример, вредност променљиве minumum вредност минимума
скупа {broj1, broj2, broj3} и ако је broj4
мањи од вредности те променљиве, тада је broj4 мањи од
најмање вредности у скупу {broj1, broj2, broj3}, што значи
да је мањи од свих вредности тог скупа и да је минимум скупа
{broj1, broj2, broj3, broj4} управо broj4.
Пошто се вредност променљиве minimum ажурира на вредност
broj4 одржава се услов да је вредност променљиве
minimum управо минимум скупа
{broj1, broj2, broj3, broj4}, тј. инваријанта је одржана.
Са друге стране, ако услов не важи, то значи да је најмањи од бројева из
скупа {broj1, broj2, broj3} мањи или једнак вредности
broj4 и то је уједно минимум скупа
{broj1, broj2, broj3, broj4}. Пошто се вредност променљиве
minimum не мења, инваријанта је опет одржана.
Као што се збир може иницијализовати нулом, а производ јединицом, што
су неутралне вредности за сабирање тј. множење, тако се и минимум може
иницијализовати вредношћу \(+\infty\),
а максимум вредношћу \(-\infty\).
Ако се ради са целобројним типом, ове вредности није
могуће представити тако да се уместо њих могу употребити вредности
numeric_limits<int>::max() и
numeric_limits<int>::min() (највећа и најмања
вредност које се могу представити типом int).
Рецимо и да се понављање кода може избећи ако би се употребила петља, што ћемо примењивати када будемо радили са дужим серијама елемената. Сви принципи алгоритма су исти и зато рад са малим серијама бројева представља одличан увод за рад са дужим серијама и петљама.
Низови и библиотечке функције
Уместо ручне имплементације одређивања минимума четири променљиве, можемо употребити низ и библиотечке функције за одређивање максимума низа. О разним врстама низова биће речи у поглављу о низовима, а до тада ћемо разматрати само низове који садрже мали број елемената и који су иницијализовани директним набрајањем њихових елемената.
У језику C++, почевши од стандарда C++-11 уведена је тзв. листа
иницијализатора (енгл. initializer list) која омогућава да се неким
функцијама проследи анониман низ сачињен од неколико елемената наведених
у витичастим заградама. За наш задатак важна је функција
min која може да прими такву листу. Тако се изразом
min({broj1, broj2, broj3, broj4}) може веома једноставно
одредити најмањи од четири дата броја.
Друга могућност је да се бројеви сместе у класичан низ или вектор и
да се употреби библиотечка функција min_element (више речи
о овоме биће у поглављу о низовима).
Основне статистике (збир, производ, просек, минумум, максимум)
Најчешће коришћени итеративни алгоритми служе за израчунавање статистика бројевних серија. На пример, једну такву серију могу чинити бројеви 1, 2, 3, 4 и 5. Најзначајније статистике су:
- збир елемената (збир бројева из примера је 15),
- производ елемената (производ бројева из примера је 120),
- минимум тј. најмањи од свих елемената (миминум бројева из примера је 1),
- максимум тј. највећи од свих елемената (максимум бројева из примера је 5).
Одређивање збира и производа
На примеру четворочлане серије елемената, прикажимо итеративне алгоритме за одређивање збира и производа. Збир четири броја се најједноставније израчунава изразом
broj1 + broj2 + broj3 + broj4што је због леве асоцијативности сабирања (у програмирању) идентично изразу
((broj1 + broj2) + broj3) + broj4Други начин да се израчунавање збира реализује је да се уведе помоћна
променљива zbir која би се увећавала за текући елемент.
zbir = broj1;
zbir = zbir + broj2;
zbir = zbir + broj3;
...За разлику од полазног решења у ком се збир израчунава само помоћу
једног израза, ово решење је итеративно, и резултат се добија
узастопном применом корака истог облика. Истакнимо још једном врло важну
особину итеративних алгоритама, а то је да се током њиховог извршавања
мења вредност неке променљиве (у овом случају то је променљива
zbir).
Уместо да збир иницијализујемо првим елементом, можемо га иницијализовати нулом, а затим увећавати за један по један елемент.
zbir = 0;
zbir = zbir + broj1;
zbir = zbir + broj2;
...Производ се одређује по веома сличном принципу, осим што уместо иницијализације нулом користимо иницијализацију јединицом (као неутралним елементом за множење) и што уместо сабирања користимо множење.
proizvod = 1;
proizvod = proizvod * broj1;
proizvod = proizvod * broj2;
...У задацима је често потребно израчунати просек тј. аритметичку средину серије елемената, која је једнака количнику збира и броја елемената. Приликом имплементације потребно је једино обратити пажњу да се пре дељења осигура да је било збир, било број елемената серије реалан број, да не би дошло до целобројног дељења.
Одређивање минимума и максимума
Потпуно аналогно израчунавању збира неколико бројева, може се израчунати минимум, једино што се уместо операције сабирања два броја користи операција одређивања минимума два броја. У сваком кораку се рачуна минимум минимума свих претходних бројева и текућег броја.
Реално је претпоставити да на располагању имамо функцију којом се
израчунава минимум два броја. Таква функција је обично део стандардне
библиотеке, а када није, једноставно се може дефинисати.
У језику C# минимум два броја може се израчунати
библиотечком функцијом Math.Min.
Минимум четири броја онда можемо одредити наредним изразом.
Math.Min(Math.Min(Math.Min(broj1, broj2), broj3), broj4)Максимум израчунавамо по потпуно истом принципу, једино што уместо минимума два броја у сваком кораку користимо максимум два броја.
И у случају налажења минимума уместо једног израза можемо дефинисати и итеративни алгоритам.
minimum = broj1;
minimum = Math.Min(minimum, broj2);
minimum = Math.Min(minimum, broj3);
...Ако би се уместо функције за рачунање минимума два броја употребило гранање (овај пут изражено условним изразом), дошло би се до следећег кода.
minimum = broj1;
minimum = broj2 < minimum ? broj2 : minimum;
minimum = broj3 < minimum ? broj3 : minimum;
...Ако би се уместо условног израза користила наредба гранања, добио би се следећи облик кода.
minimum = broj1;
if (broj2 < minimum)
minimum = broj2;
else
minimum = minimum;
if (broj3 < minimum)
minimum = broj3;
else
minimum = minimum;
...Јасно је да гране else немају никакав ефекат и могу се
изоставити. Тиме добијамо уобичајени алгоритам одређивања минимума.
minimum = broj1;
if (broj2 < minimum)
minimum = broj2;
if (broj3 < minimum)
minimum = broj3;
...Дакле, променљиву minimum иницијализујемо вредношћу
првог броја, а затим је редом поредимо са другим, трећим, четвртим и
петим бројем и када год је неки од тих бројева мањи од дотадашње
вредности минимума тј. вредности променљиве minimum,
ажурирмо вредност те променљиве и постављамо је на број за који смо
открили да је мањи од ње.
Можемо и мало прецизније да анализирамо претходни кôд и да докажемо
његову коректност. У првом кораку вредност променљиве
minimum биће минимум једночланог скупа
{broj1}, у другом биће минимум двочланог скупа
{broj1, broj2}, након трећег биће минимум скупа
{broj1, broj2, broj3} и тако даље. Такав услов, дакле, важи
у сваком кораку нашег програма и назива се инваријанта. Ако је,
на пример, вредност променљиве minumum вредност минимума
скупа {broj1, broj2, broj3} и ако је broj4
мањи од вредности те променљиве, тада је broj4 мањи од
најмање вредности у скупу {broj1, broj2, broj3}, што значи
да је мањи од свих вредности тог скупа и да је минимум скупа
{broj1, broj2, broj3, broj4} управо broj4.
Пошто се вредност променљиве minimum ажурира на вредност
broj4 одржава се услов да је вредност променљиве
minimum управо минимум скупа
{broj1, broj2, broj3, broj4}, тј. инваријанта је одржана.
Са друге стране, ако услов не важи, то значи да је најмањи од бројева из
скупа {broj1, broj2, broj3} мањи или једнак вредности
broj4 и то је уједно минимум скупа
{broj1, broj2, broj3, broj4}. Пошто се вредност променљиве
minimum не мења, инваријанта је опет одржана.
Као што се збир може иницијализовати нулом, а производ јединицом, што
су неутралне вредности за сабирање тј. множење, тако се и минимум може
иницијализовати вредношћу \(+\infty\),
а максимум вредношћу \(-\infty\).
Ако се ради са целобројним типом, ове вредности није
могуће представити тако да се уместо њих могу употребити вредности
int.MaxValue и int.MinValue (највећа и најмања
вредност које се могу представити типом int).
Рецимо и да се понављање кода може избећи ако би се употребила петља, што ћемо примењивати када будемо радили са дужим серијама елемената. Сви принципи алгоритма су исти и зато рад са малим серијама бројева представља одличан увод за рад са дужим серијама и петљама.
Низови и библиотечке функције
Уместо ручне имплементације одређивања минимума четири променљиве, можемо употребити низ и библиотечке функције за одређивање максимума низа. О разним врстама низова биће речи у поглављу о низовима, а до тада ћемо разматрати само низове који садрже мали број елемената и који су иницијализовани директним набрајањем њихових елемената.
У језику C# низ који садржи пет бројева се може дефинисати на следећи начин.
int[] a = {broj1, broj2, broj3, broj4, broj5};Дакле, тип низ целих бројева се означава са
int[], а приликом иницијализације елемената они се наводе у
витичастим заградаима. Могуће је у старту само навести број елемената,
па тек касније попуњавати један по један елемент (тада се приликом
иницијализације елементи постављају на подразумевану вредност свог типа,
што је у случају целих бројева нула).
int[] a = new int[5];
a[0] = int.Parse(Console.ReadLine());
a[1] = int.Parse(Console.ReadLine());
...Приметимо да бројање позиција елемената низа почиње увек од нуле!
Када је низ дефинисан, збир и минимум његових елемената можемо веома
једноставно одредити методама Sum и Min које
припадају библиотеци Linq (стога се на почетку програма мора
навести и директива using System.Linq;). Ова библиотека ће
бити детаљно описана у поглављу збирке посвећеном низовима.
using System.Linq;
...
int zbir = a.Sum(); // odredjuje zbir svih elemenata niza
int minimum = a.Min(); // odredjuje minimum svih elemenata niza